package graph;

public class Graph {

	int vertexCount;
	int type;
	//使用邻接矩阵来表示
	int[][] adjMatrix;
	
	//初始化邻接矩阵
	public Graph(int n, int type) {
		vertexCount = n;
		this.type = type;
		adjMatrix = new int[n][n];
	}
	
	//判断图的类型
	public int getType(){
		return type;
	}
	
	//获取图的顶点数
	public int getVertexCount(){
		return vertexCount;
	}
	
	//获取边的条数
	public int getEdgeCount(){
		int count = 0;
		for(int i = 0; i < vertexCount; i++){
			for(int j = 0; j < vertexCount; j++){
				if(adjMatrix[i][j] != 0){
					count++;
				}
			}
		}
		//如果是无向图，还要除以2
		if(type == 0){
			count /= 2; 
		}
		return count;
	}
	
	//序号为u和v的两个点之间插入边
	public void insertEdge(int u, int v){
		if(type == 0){
			adjMatrix[u - 1][v - 1] = 1;
			adjMatrix[v - 1][u - 1] = 1;
		}else{
			adjMatrix[u][v] = 1;
		}
	}
	
	//删除边
	public void deleteEdge(int u, int v){
		if(type == 0){
			adjMatrix[u - 1][v - 1] = 0;
			adjMatrix[v - 1][u - 1] = 0;
		}else{
			adjMatrix[u - 1][v - 1] = 0;
		}
	}
	
	//判断两个顶点是否相连
	public boolean isAdjacent(int u, int v){
		return adjMatrix[u][v] == 1;
	}
	/**
	 * 计算顶点的度
	 */
	public int getDegree(int u){
		int degree = 0;
		if(type == 0){
			for (int j = 0; j < vertexCount; j++) {
				if (adjMatrix[u - 1][j] != 0) {
					degree++;
				}
			}
		}else{
			//有向图的度为出度和入度之和
			for (int j = 0; j < vertexCount; j++) {
				if (adjMatrix[u - 1][j] != 0) {
					degree++;
				}
			}
			for (int i = 0; i < vertexCount; i++) {
				if (adjMatrix[i][u - 1] != 0) {
					degree++;
				}
			}
		}
		return degree;
	}
	
	//获取入度
	public int getInDegree(int u){
		int degree = 0;
		if(type == 0){
			System.err.println("无向图没有出度和入度");
		}else{
			for (int i = 0; i < vertexCount; i++) {
				if (adjMatrix[i][u - 1] != 0) {
					degree++;
				}
			}
		}
		return degree;
	}
	
	//获取出度
	public int getOutDegree(int u){
		int degree = 0;
		if(type == 0){
			System.err.println("无向图没有出度和入度");
		}else{
			for (int j = 0; j < vertexCount; j++) {
				if (adjMatrix[u - 1][j] != 0) {
					degree++;
				}
			}
		}
		return degree;
	}
}
